package alibaba.algorithm;

import pojo.ListNode;
import pojo.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

public class Answer {
    private static  ListNode res2 = null;
    /**
     * 剑指 Offer II 024. 反转链表
     * 1->2->null
     * 2->1->null
     * 关键之处在于知道如何去拼接目标链表
     */
    public static ListNode reverseList(ListNode head) {
        ListNode res = null;
        while (head != null) {
            ListNode tmp = head.next;
            //拼接目标链表
            head.next = res;
            res = head;
            //保存下次循环对象
            head = tmp;
        }
        return res;
    }
    //递归
    public static ListNode reverseList2(ListNode head) {
        if (head != null)  {
            ListNode tmp = head.next;
            //拼接目标链表
            head.next = res2;
            res2 = head;
            //保存下次循环对象
            head = tmp;
            reverseList2(head);
        }
        return res2;
    }

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     */
    public static int search(int[] nums, int target) {
        //找到target左边
        int left = 0;
        int right = nums.length -1;
        while (left <= right) {
            int mid = (left + right)/2;
             if (nums[mid] < target) {
                left = mid +1;
            } else {
                right = mid -1;
            }
        }
        int leftTarget =  right;
        //找到target右边
        left = 0;
        right = nums.length -1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (nums[mid] <= target) {
                left = mid +1;
            } else {
                right = mid -1;
            }
        }
        int rightTarget =  left;
        return rightTarget - leftTarget -1 ;
    }

    /**
     * 53. 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 子数组 是数组中的一个连续部分。
     * 示例 1：
     *
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     */
    public static int maxSubArray(int[] nums) {
        Integer maxSum = null;
        int nowSum = 0;
        int beforeSum = 0;
        for (int num : nums) {
            //比较上一个和，小于0丢弃
            if (beforeSum < 0) {
                nowSum = 0;
                beforeSum = 0;
            }
            //计算当前和
            nowSum = beforeSum + num;

            if (maxSum == null || nowSum > maxSum) {
                maxSum = nowSum;
            }
            beforeSum = nowSum;
        }
        return maxSum;
    }


    /**
     * 92. 反转链表 II
     * 给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     *
     *
     * 示例 1：
     *
     *
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     *
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode leftHead = null;
        ListNode pre = null;
        int idx = 1;
        for (ListNode cur = head;cur != null;cur = cur.next) {
            if (idx++ == left) {
                pre = cur;
                break;
            }
            leftHead = cur;
        }
        ListNode mid = null;
        while (pre != null) {
            ListNode tmp = pre.next;
            if (idx++ <= right) {
                pre.next = mid;
                mid = pre;
            } else {
                mid.next = pre;
                break;
            }
            tmp = pre;
        }
        leftHead.next = mid;
        return leftHead;
    }

    /**
     * 110\. 平衡二叉树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     *
     * 本题中，一棵高度平衡二叉树定义为：
     *
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     * 输入：root = [3,9,20,null,null,15,7]  isBalanced(new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7))))
     * 输出：true
     */
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public static Integer height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    /**
     * 94. 二叉树的中序遍历
     *
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        list = visit(root, list);
        return list;
    }

    public static List<Integer> visit(TreeNode root, List<Integer> list) {
        if (root != null) {
            visit(root.left, list);
            list.add(root.val);
            visit(root.right, list);
        }
        return list;
    }

    /**
     * 617. 合并二叉树
     * 给你两棵二叉树： root1 和 root2 。
     *
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     *
     * 返回合并后的二叉树。
     *
     * 注意: 合并过程必须从两个树的根节点开始。
     *
     * 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
     * 输出：[3,4,5,5,4,null,7]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/merge-two-binary-trees
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode res = new TreeNode();
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        res.val = root1.val + root2.val;
        res.left = mergeTrees(root1.left,root2.left);
        res.right = mergeTrees(root1.right,root2.right);
        return res;
    }
    /**
     * 102. 二叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int levelSize = queue.size();
            for (int i = 1;i<= levelSize;i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    level.add(node.val);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
            }
            res.add(level);
        }
        return res;
    }

    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * @param nums
     * @return
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     *
     *  
     *
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     *  
     *
     * 示例 1:
     *
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int majorityElement(int[] nums) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>(64);
        for (int num : nums) {
            //统计num的个数
            map.merge(num, 1, Integer::sum);
        }
        for (int key : map.keySet()) {
            if (map.get(key) > nums.length / 2) {
                res = key;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)));
        queue.size();
    }
}
